


// 下面的代码是有问题的：
// root@educoder:/data/workspace/myshixun/step# ./test 
// 6
// 8 3 90 47 1 2
// 8编码为001
// 3编码为0000
// 90编码为1
// 47编码为01
// 1编码为00010
// 2编码为00011
// Segmentation fault (core dumped)


// debug：
// 最终在 Linux 上测试，是因为有 Segmentation fault (core dumped) :
// 1. 编写当前文件的 makefile 文件：gcc test.c -o test -g  # -g3 也是可以的(使得等下的 gdb 调试的时候会显示报错的行号的哦)
// 2. make 一下就生成了当前文件的可执行文件 test
// 3. ./test 再输入测试用例就会报  Segmentation fault (core dumped)  的错误，同时生成 core 报错文件
// 4. 用 gdb 调试 core 文件：gdb test core.4644
// 5. 再 bt 或者 where 就可以看到当前文件在那个地方出现了内存问题，可以看到行号


// 最终确定是下面的范围越界了
// for (int i = 1; i <= sizeof(HC) + 1; i++) {   // 注意不要越界
for (int i = 1; i < sizeof(HC) - 1; i++) {

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

typedef struct
{
	int weight;
	int parent, lchild, rchild;
}HTNode, * HuffmanTree;
typedef char** HuffmanCode;

void Select(HuffmanTree HT, int len, int* s1, int* s2)
{
	int i, min1 = 0x3f3f3f3f, min2 = 0x3f3f3f3f;//先赋予最大值
	for (i = 1; i <= len; i++)
	{
		if (HT[i].weight < min1 && HT[i].parent == 0)
		{
			min1 = HT[i].weight;
			*s1 = i;
		}
	}
	int temp = HT[*s1].weight;//将原值存放起来，然后先赋予最大值，防止s1被重复选择
	HT[*s1].weight = 0x3f3f3f3f;
	for (i = 1; i <= len; i++)
	{
		if (HT[i].weight < min2 && HT[i].parent == 0)
		{
			min2 = HT[i].weight;
			*s2 = i;
		}
	}
	HT[*s1].weight = temp;//恢复原来的值
}

//用算法5.10构造赫夫曼树
void CreatHuffmanTree(HuffmanTree* HT, int n)
{
	//构造赫夫曼树HT
	int m, s1, s2, i;
	if (n <= 1) return;
	m = 2 * n - 1;
	*HT = (HTNode*)malloc(sizeof(HTNode) * (m + 1));  		//0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根结点
	if (*HT == NULL) return;
	for (i = 1; i <= m; ++i)        	//将1~m号单元中的双亲、左孩子，右孩子的下标都初始化为0
	{
		(*HT)[i].parent = 0;  (*HT)[i].lchild = 0;  (*HT)[i].rchild = 0;
	}
	for (i = 1; i <= n; ++i)        	//输入前n个单元中叶子结点的权值
		scanf("%d", &((*HT)[i].weight));
	//――――――――――初始化工作结束，下面开始创建赫夫曼树――――――――――
	for (i = n + 1; i <= m; ++i)
	{  	//通过n-1次的选择、删除、合并来创建赫夫曼树
		Select(*HT, i - 1, &s1, &s2);
		//在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,
		// 并返回它们在HT中的序号s1和s2
		(*HT)[s1].parent = i;
		(*HT)[s2].parent = i;
		//得到新结点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i
		(*HT)[i].lchild = s1;
		(*HT)[i].rchild = s2;							//s1,s2分别作为i的左右孩子
		(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight; 	//i 的权值为左右孩子权值之和
	}												//for
}
// CreatHuffmanTree
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode* HC, int n)
{
	//从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中
	int i, start, c, f;
	*HC = (char**)malloc(sizeof(char*) * (n + 1));         						//分配n个字符编码的头指针矢量
	if (*HC == NULL) return;
	char* cd = (char*)malloc(sizeof(char) * n);							//分配临时存放编码的动态数组空间
	if (cd == NULL) return;
	cd[n - 1] = '\0';                            		//编码结束符
	for (i = 1; i <= n; ++i)
	{                      							//逐个字符求赫夫曼编码
		start = n - 1;                          		//start开始时指向最后，即编码结束符位置
		c = i;
		f = HT[i].parent;                 			//f指向结点c的双亲结点
		while (f != 0)
		{                          					//从叶子结点开始向上回溯，直到根结点
			--start;                          		//回溯一次start向前指一个位置
			if (HT[f].lchild == c)
				cd[start] = '0';						//结点c是f的左孩子，则生成代码0
			else
				cd[start] = '1';                 		//结点c是f的右孩子，则生成代码1
			c = f;
			f = HT[f].parent;             			//继续向上回溯
		}                                  			//求出第i个字符的编码      
		(*HC)[i] = (char*)malloc(sizeof(char) * (n - start));         			// 为第i 个字符编码分配空间
		if ((*HC)[i] == NULL) return;
		strcpy((*HC)[i], &cd[start]);        			//将求得的编码从临时空间cd复制到HC的当前行中
	}
	free(cd);                            			//释放临时空间
}													// CreatHuffanCode
void show(HuffmanTree HT,  HuffmanCode HC)
{
	// for (int i = 1; i <= sizeof(HC) + 1; i++) {   // 注意不要越界
	for (int i = 1; i < sizeof(HC) - 1; i++) {
		// cout << HT[i].weight << "编码为" << HC[i] << endl;
		printf("%d编码为%s\n", HT[i].weight, HC[i]);
	}
}

int main()
{
	HuffmanTree HT;
	HuffmanCode HC;
	int n;
	scanf("%d", &n);											//输入赫夫曼树的叶子结点个数
	CreatHuffmanTree(&HT, n);
	CreatHuffmanCode(HT, &HC, n);
	show(HT, HC);

	return 0;
}


